#ifndef __COINCHANGE__
#define __COINCHANGE__
#include <vector>
#include <algorithm>
using namespace std;

typedef struct Coin {
	int Value;
	int Count;
};

bool CompareCoinByValue(const Coin& coin1, const Coin& coin2) {
	return coin1.Value > coin2.Value;
}

/*
* 题目：指定币值和相应的数量，用最少的数量凑齐某金额。
* 思路：利用贪心算法，我们优先选择面值大的钱币，以此类推，直到凑齐总金额。
*/
vector<int> CoinChange(int total, vector<Coin>& coins) {
	vector<int> result(coins.size(), 0);

	//根据面值进行排序
	//降序排序
	sort(coins.begin(), coins.end(), CompareCoinByValue);
	for (int i = 0; i < coins.size(); i++) {
		int count = total / coins[i].Value;

		if (count > coins[i].Count) {
			result[i] = coins[i].Count;
			total -= (coins[i].Value * coins[i].Count);
		}

		else if (count < coins[i].Count) {
			result[i] = count;
			total -= (coins[i].Value * count);
		}
			
		else {
			result[i] = coins[i].Count;
			break;
		}
	}
	return result;
}

#endif // !__COINCHANGE__
